package com.faiz.algorithm;

import java.util.Arrays;
import java.util.List;

public class WordBreak {
    boolean res = false;
    public boolean wordBreak(String s, List<String> wordDict) {
        //简单思路：回溯算法
        StringBuffer sb = new StringBuffer();
        wordBreak(s, wordDict, sb);
        return res;
    }

    public void wordBreak(String s, List<String> wordDict, StringBuffer sb) {
        if (!s.startsWith(sb.toString()) || sb.toString().length() > s.length() || res) {
            return;
        }
        if (s.equals(sb.toString())) {
            res = true;
            return;
        }
        for (String word : wordDict) {
            sb.append(word);
            wordBreak(s, wordDict, sb);
            sb.delete(sb.length() - word.length(), sb.length());
        }
    }

    public static void main(String[] args) {
        WordBreak wordBreak = new WordBreak();
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak.wordBreak("leetcode", wordDict));

    }

}
